package main

/**
 *
 * @param S string字符串
 * @param T string字符串
 * @return string字符串
 */
func minWindow(S string, T string) string {
	// write code here
	left, right := 0, 0             //表示窗口左右位置的指针
	start := 0                      //start 表示最后结果字符串开始位置
	var minLen int = 1e9            // minlen表示最后字符串长度，二者可以表示一个字符串
	var need = make(map[byte]int)   //need的存放字符串T的所有字符统计
	var window = make(map[byte]int) //window 存放现有的窗口中出现在need中的字符统计
	match := 0                      //window与need的匹配度
	for _, v := range T {
		need[byte(v)]++
	}

	for right < len(S) {
		for match < len(need) && right < len(S) {
			c1 := S[right]
			if _, ok := need[c1]; ok {
				window[c1]++
				if window[c1] == need[c1] {
					match++
				}
			}
			right++
		}
		for match == len(need) {
			//当匹配度等于need,说明这段区间可以作为候选结果，更新ret
			if right-left < minLen {
				minLen = right - left
				start = left
			}
			c2 := S[left]
			if _, ok := need[c2]; ok {
				window[c2]--
				if window[c2] < need[c2] {
					match--
				}
			}
			left++
		}
	}
	if minLen == 1e9 {
		return ""
	} else {
		return S[start : start+minLen]
	}
}
